package com.ry.day1129;
import java.util.*;

public class LC120 {

    static class Solution {
        /**
         * @param start: a string
         * @param end:   a string
         * @param dict:  a set of string
         * @return: An integer
         */
        public int ladderLength(String start, String end, Set<String> dict) {
            if(dict ==null) return 0;
            if(start.equals(end)) return 1;
            dict.add(end); // dict可能没有end,但是有end的上一个word
            Queue<String> q = new LinkedList<>();
            Set<String> set = new HashSet<>();
            q.add(start);

            int ans =1;
            while (!q.isEmpty()){
                ans++;

                int size = q.size();
                for (int i = 0; i <size ; i++) {
                    String cur = q.poll();
                    List<String> nexts = getNextWords(cur.toCharArray(),dict);
                    for (String next : nexts) {
                        if(set.contains(next)) continue;
                        if(next.equals(end)) return ans;
                        set.add(next);
                        q.add(next);
                    }
                }
            }
            return ans;
        }

        public List<String> getNextWords(char[] arr,Set<String> dict){
            List<String> ans = new ArrayList<>();
            for (int i = 0; i <arr.length ; i++) {
                char bak = arr[i];
                for(char c='a';c<='z';c++){
                    if(arr[i] ==c) continue;
                    arr[i] = c;
                    String s2 = new String(arr);
                    if(dict.contains(s2)){
                        ans.add(s2);
                    }
                }
                arr[i] =bak;
            }
            return ans;
        }

    }

    public static void main(String[] args) {
        Set<String> s1 = new HashSet<>();
        s1.add("a");
        s1.add("b");
        s1.add("c");

        Solution obj = new Solution();
        System.out.println(obj.ladderLength("a","c",s1));

        s1.clear();
        s1.add("hot");s1.add("dot");s1.add("dog");s1.add("lot");s1.add("log");
        System.out.println(obj.ladderLength("hit","cog",s1));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
120 · 单词接龙
算法
困难
通过率
33%

题目
题解99
笔记
讨论99+
排名
记录
描述
给出两个单词（start和end）和一个字典，找出从start到end的最短转换序列，输出最短序列的长度。

变换规则如下：

每次只能改变一个字母。
变换过程中的中间单词必须在字典中出现。(起始单词和结束单词不需要出现在字典中)
最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
l
e
n
(
d
i
c
t
)
<
=
5000
,
l
e
n
(
s
t
a
r
t
)
<
5
len(dict)<=5000,len(start)<5
样例
样例 1：

输入：

start = "a"
end = "c"
dict =["a","b","c"]
输出：

2
解释：

"a"->"c"

样例 2：

输入：

start ="hit"
end = "cog"
dict =["hot","dot","dog","lot","log"]
输出：

5
解释：

"hit"->"hot"->"dot"->"dog"->"cog"

相关知识
学习《2024年9月北美大厂最新面试真题精讲》课程中的1.6Amazon：最新面试精选003相关内容 ，了解更多相关知识！
标签
相关题目

121
单词接龙 II
困难
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
46/1591
已开启智能提示
发起考试
45 分 00 秒
1234567891011


    控制台
            历史提交

 */
